﻿
/*********************************************************************************************
 * VARIABLES AND CONSTANTS
 *********************************************************************************************/
//For common using
var around = [
              [-1, -1],
              [-1, 1],
              [1, -1],
              [1, 1],
              [-1, 0],
              [0, -1],
              [0, 1],
              [1, 0],
              [0, 0]
               ];
var aroundLength = around.length - 1;

//For setting start, finish cell
const SETTING_NOTHING = 0;
const SETTING_START = 1;
const SETTING_FINISH = 2;
var isSetting = SETTING_NOTHING;

//For tracing path
const TRACING_SPEED = 200;

//For creating custom path
var lastestX, lastestY, lastestFunc;
var aroundCustomCell;
var customPathCost;

//Main variables
const SPEED = 200;
const DELAY = SPEED/2;
const OPTIMIZE = false;
var costIsDistance = true;
var startIndex = 0;
var traceMap;
var queue;
var globalStart = new Coordinate(-1, -1, 0);
var globalFinish = new Coordinate(-1, -1, 0);
var heuristicFunction;
var turn = 0;
var heuristicWasInitialized = false;
const sqrt2 = getExactNumDigits(Math.sqrt(2), 2);
var loopsCount, expandCount;

/*********************************************************************************************
 * FUNCTIONS
 *********************************************************************************************/
function getMapCell(x, y){
	return document.getElementById("mapTable").children[0].children[x+1].children[y+1];
}

function nodesEqual(a, b){
	if(a == null || b ==  null){
		return false;
	}
	return (a.x === b.x && a.y === b.y);
}

function isStart(a){
	return nodesEqual(a, globalStart);
}

function isFinish(a){
	return nodesEqual(a, globalFinish);
}

function isInMap(x, y){
	if(x<0 || x>=m){
		return false;
	}
	if(y<0 || y>=n){
		return false;
	}
	return true;
}

function walkable(x, y){
	if(!isInMap(x, y)){		
		return false;
	}
	switch(terrain[x][y]){
		case 0:
			return true;
		default:
			return false;
	}
}

function doesPathExist(fromX, fromY, toX, toY){
	if(walkable(fromX, fromY) && walkable(toX, toY)){
		/*
		//SIMPLE - allow go through the single wall when go diagonally.
		return true;
		*/								
						
		if(Math.abs(fromX - toX) + Math.abs(fromY - toY) === 2){
			var t1 = walkable(fromX, toY) === true ? 1 : 0;
			var t2 = walkable(toX, fromY) === true ? 1 : 0;					
			if(t1+t2 === 0){
				return false;
			} else{
				return true;
			}
		} else {
			return true;
		}
		
	}	
	return false;
}

function costToMove(fromX, fromY, toX, toY){	
	if(Math.abs(fromX - toX) + Math.abs(fromY - toY) === 2){
		return getExactNumDigits(Math.sqrt(2), 2);
	} else {
		return 1;
	}
}

function getArrow(fromX, fromY, toX, toY){
	if(fromX < toX) {
		if(fromY < toY) {
			return "se";	
		} else if(fromY == toY) {
			return "s";
		} else {
			return "sw";
		}
	} else if(fromX == toX) {
		if(fromY < toY) {
			return "e";
		} else {
			return "w";
		}
	} else {
		if(fromY < toY) {
			return "ne";	
		} else if(fromY == toY) {
			return "n";
		} else {
			return "nw";
		}
	}
	return "";
}

function beginSettingStart(x, y){
	isSetting = SETTING_START;
	document.body.className = "start";
	if(x!=-1 && y!=-1) {						
		getMapCell(x, y).className = "";						
	}			
}

function endSettingStart(x, y){			
	isSetting = SETTING_NOTHING;
	getMapCell(x, y).className = "start";
	document.body.className = "normal";
	var f = document.route;
	f.fromX.value = x;
	f.fromY.value = y;
}

function beginSettingFinish(x, y){
	isSetting = SETTING_FINISH;			
	document.body.className = "finish";
	if(x!=-1 && y!=-1) {
		getMapCell(x, y).className = "";
	}
}

function endSettingFinish(x, y){
	isSetting = SETTING_NOTHING;
	getMapCell(x, y).className = "finish";
	document.body.className = "normal";
	var f = document.route;
	f.toX.value = x;
	f.toY.value = y;
}

function onCellClick(x, y){
	//alert("click on (" + x + ", " + y +"), isSetting = " + isSetting);
	var c = getMapCell(x, y).className;
	if(c == "start") {
		if(isSetting == SETTING_NOTHING) {
			//alert("1");
			beginSettingStart(x, y);
		} else  if(isSetting == SETTING_START && walkable(x, y)) {
			//alert("2");
			endSettingStart(x, y);
		}
	} else if(c == "finish") {
		if(isSetting == SETTING_NOTHING) {
			//alert("3");
			beginSettingFinish(x, y);
		} else if(isSetting == SETTING_FINISH && walkable(x, y)) {
			//alert("4");
			endSettingFinish(x, y);
		}
	} else {
		if(isSetting == SETTING_START && walkable(x, y)) {
			//alert("5");
			endSettingStart(x, y);
		} else if(isSetting == SETTING_FINISH && walkable(x, y)) {
			//alert("6");
			endSettingFinish(x, y);
		}
	}
}

function tracePath(found, traceMap, iTime){
	for(var i=0; i<m; ++i){
		for(var j=0; j<n; ++j){
			map[i][j].isInPath = false;
		}
	}
	
	var isBuilt = true;
	var extraTime = SPEED * iTime;
	if(found == true){		
		var i = 0;
		var t = globalFinish;
		document.getElementById("cost").innerHTML = "Chi phí: " + getExactNumDigits(t.cost, 2) + ((costIsDistance) ? " chiều dài đơn vị" : " bước");
		setTimeout("getMapCell("+t.x+", "+t.y+").className = \'finish\';", TRACING_SPEED*(++i) + extraTime);
		logDebug("TRACE PATH to ("+t.x+", "+t.y+")");
		while(!nodesEqual(t, globalStart)){
			var beforeT = traceMap[t.x][t.y];
			if(beforeT.isInPath == true){
				alert("Đường đi không thể xây dựng được (tạo thành chu trình)");
				isBuilt = false;
				break;
			} else {
				beforeT.isInPath = true;
			}
			//document.write((t.x+1) + ", " + (t.y+1) + "<br/>");
			setTimeout("getMapCell("+beforeT.x+", "+beforeT.y+").className = getArrow("+beforeT.x+", "+beforeT.y+", "+t.x+", "+t.y+");", TRACING_SPEED*(++i) + extraTime);			
			t = beforeT;
			logDebug("<- ("+t.x+", "+t.y+")");
		}
		if(isBuilt){
			setTimeout("getMapCell("+t.x+", "+t.y+").className = \'start\';", TRACING_SPEED*(++i) + extraTime);
		}
	} else {
		setTimeout('alert("Không tìm thấy đường đi!");', extraTime);
	}
}

function statistic(iTurn, iCost, iExamine, iExpand, iTime){
	//alertDebug(iTurn + " " + iCost + " " + iExamine + " " + iExpand + " " + iTime);
	var tbl = document.getElementById("statisticTable");
	//alertDebug(tbl.innerHTML);
	var newRow = Node("tr", new Array());
	var turnD = Node("td", new Array(), ""+iTurn);						
	var costD = Node("td", new Array(), (iCost == INFINITY ? "Không tồn tại" : (""+getExactNumDigits(iCost, 2))));
	var examineD = Node("td", new Array(), ""+iExamine);
	var expandD = Node("td", new Array(), ""+iExpand);
	var timeD =Node("td", new Array(), ""+iTime);
	appendNodes(newRow, new Array(turnD, costD, examineD, expandD, timeD));
	//alertDebug(newRow.innerHTML);			
	tbl.appendChild(newRow);
}

function CustomPathCell(x, y, onclickFunc){
	this.x = x;
	this.y = y;
	this.onclickFunc = onclickFunc;
}		
function beginCreatePath(){	
	var f = document.route;
	if(f.fromX.value === "-1" || f.fromY.value === "-1" || f.toX.value === "-1" || f.toY.value === "-1"){
		return;
	}			
	aroundCustomCell = [];
	customPathCost = 0;
	globalStart.x = eval(f.fromX.value);
	globalStart.y = eval(f.fromY.value);
	globalFinish.x = eval(f.toX.value);
	globalFinish.y = eval(f.toY.value);
	updateLastestCell(globalStart.x, globalStart.y);
}

function updateLastestCell(x, y){	
	//Reset old cells
	var n = aroundCustomCell.length;
	for(var i=0; i<n; ++i){
		var t = aroundCustomCell[i];
		getMapCell(t.x, t.y).children[1].src = "";
		getMapCell(t.x, t.y).setAttribute("onclick", t.onclickFunc);
	}
		
	//Prepare to set new Cells						
	if(x != globalStart.x || y != globalStart.y){
		customPathCost += costToMove(lastestX, lastestY, x, y);
		if(x != globalFinish.x || y != globalFinish.y){
			getMapCell(x, y).children[1].src = "Images/2ring.png";
		}
	}
	lastestX = x;
	lastestY = y;
	//alertDebug("new: " + x + " " + y);
	if(x == globalFinish.x && y == globalFinish.y){
		customPathCost = getExactNumDigits(customPathCost, 2);
		alert("Đã tới đích!\nChi phí: " + customPathCost);
		return;
	}			
	
	//Set new cells			
	aroundCustomCell.length = 0;
	for(var i=startIndex; i<aroundLength; ++i){
		var x = lastestX + around[i][0];
		var y = lastestY + around[i][1];				
		if(doesPathExist(lastestX, lastestY, x, y) && (x != globalStart.x || y != globalStart.y)){
			var t = getMapCell(x, y);
			//alertDebug(x+" " + y + " " + t.children[1].getAttribute("src"));
			if(t.children[1].getAttribute("src") == "Images/2ring.png"){
				//alertDebug(x + " " + y + " is 2ring");
				continue;
			}
			//alertDebug("Save status of " + x + " " + y);	
			aroundCustomCell.push(new CustomPathCell(x, y, t.getAttribute("onclick")));
			getMapCell(x, y).setAttribute("onclick", "updateLastestCell("+x+", "+y+");");
			if(x != globalFinish.x || y != globalFinish.y){
				t.children[1].src = "Images/1ring.png";
			}
		}				
	}
}

function log(msg){
	document.getElementById("log").innerHTML += msg + "\n";
}

function min(a, b){
	if(a < b){
		return a;
	} else {
		return b;
	}
}

function manhattan(a, b){
	return Math.abs(a.x - b.x) + Math.abs(a.y -b.y);
}

function diagonal(a, b){
	return min(Math.abs(a.x - b.x), Math.abs(a.y - b.y)) + Math.abs(Math.abs(a.x - b.x) - Math.abs(a.y - b.y));
}

function euclid(a, b){
	return Math.sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

function diagonalAndEuclid(a, b){
	return min(Math.abs(a.x - b.x), Math.abs(a.y - b.y))*Math.sqrt(2) + Math.abs(Math.abs(a.x - b.x) - Math.abs(a.y - b.y));
}

function heuristic(a){
	return heuristicFunction(a, globalFinish);
}

function setHeuristicFunction(functionName){
	switch (functionName) {
		case "manhattan": 
			heuristicFunction = manhattan;
			break;
		case "diagonal":
			heuristicFunction = diagonal;
			break;
		case "euclid": 
			heuristicFunction = euclid;
			break;		
		default:
			heuristicFunction = diagonalAndEuclid;		
	}
}

function setCostType(type){
	if(type=="steps"){
		costIsDistance = false;
	} else {
		costIsDistance = true;
	}
}

function setDirections(directions){	
	if(directions == "4"){
		startIndex = 4;
	} else {
		startIndex = 0;
	}
}

function showArrowMap() {
	var table = Node("table", new Array("class", "map", "id", "arrowMap"));	
	for(var i=0; i<m; ++i) {
		var tr = Node("tr", new Array());
		for(var j=0; j<n; ++j) {
			var td;
			if (terrain[i][j] == 0) {
				if(traceMap[i][j] == undefined) {
					td = Node("td", new Array());
				} else {
					td = Node("td", new Array("class", getArrow(traceMap[i][j].x, traceMap[i][j].y, i, j) + "2"));
				}
			} else {
				td = Node("td", new Array("class", "wall"));
			}
			tr.appendChild(td);
		}
		table.appendChild(tr);
	}
	
	document.body.appendChild(table);
}

function hideArrowMap() {
	if(document.getElementById("arrowMap")) {
		document.body.removeChild(document.getElementById("arrowMap"));
	}
}